package main
import (
	"fmt"
	"time"
)
//插入排序算法
//插入时排序属于内部排序法，是将欲排序的元素以插入的方式找到该元素的适当位置，以达到排序的目的

//思想： 把n个待排序的元素堪称为一个有序表和无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，
//		排序过程中每次从无序表取出第一个元素，把它的排序码一次与有序表元素的排序码进行比较，
//		将它插入到有序表中的适当位置，使之成为新的有序表。

func main(){
	var array [10]int = [...]int{11,2,42,21,4,64,14,50,91,16}
	fmt.Println(array)
	start := time.Now().UnixNano()
	InsertSort(&array)
	end := time.Now().UnixNano()
	fmt.Println(array)
	fmt.Println("所用时间：",end - start)
}

func InsertSort(a *[10]int){
	//从大到小排
	for i := 1;i< len(a);i++{		//将从第2个元素开始与前面的有序段进行比较，如果比前第InsertIndex个大就把前InsertIndex个后移然后把自己填上去，否则就插入在原位。
		InsertVal := a[i]	
		InsertIndex := i-1			//当前元素的前一个元素的下标
		for InsertIndex >= 0 && a[InsertIndex] < InsertVal{  //将当前元素与第前InsertIndex个比较 小就往后移，然后继续向前比较		
			a[InsertIndex+1] = a[InsertIndex]
			InsertIndex--	
		}
		if InsertIndex + 1 != i{
			a[InsertIndex+1] = InsertVal	//如果前一个比当前元素大就InsertIndex后退一格然后插入
		}
	}
}